/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月06日
*   描    述：
*
================================================================*/

/*
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * 示例 1：
 *   输入：nums = [1,2,0]
 *   输出：3
 *
 * 示例 2：
 *   输入：nums = [3,4,-1,1]
 *   输出：2
 *
 * 示例 3：
 *   输入：nums = [7,8,9,11,12]
 *   输出：1
 *
 * 提示：
 *   1 <= nums.length <= 5 * 105
 *   -231 <= nums[i] <= 231 - 1
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void swap(int* nums, int index1, int index2) {
  int temp = nums[index1];
  nums[index1] = nums[index2];
  nums[index2] = temp;
}

/*
 * 算法思想如下：
 *   遍历数组，将每个正数放置在正确的位置上。即，如果当前元素是正数且在有效范围内（1 到数组长度之间），将其交换到应该放置的位置上（例如，数值为 k 的元素应该放置在数组的第 k-1 个位置上）。
 *   再次遍历数组，找到第一个位置上数值不等于索引加 1 的元素，返回该位置加 1。
 *   如果数组中的所有元素都在正确的位置上，即没有缺失的正数，返回数组长度加 1。
 */
int firstMissingPositive(int* nums, int numsSize) {
  for (int i = 0; i < numsSize; i++) {
    while (nums[i] > 0 && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
      swap(nums, i, nums[i] - 1);
    }
  }

  for (int i = 0; i < numsSize; i++) {
    if (nums[i] != i + 1) {
      return i + 1;
    }
  }
  
  return numsSize + 1;
}

int main() {
  int nums[] = {0, 1, 2};
  int ret = firstMissingPositive(nums, sizeof(nums) / sizeof(nums[0]));
  printf("%d\n", ret);
  return 0;
}